I did this without queues. Only maps.

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.hits = {}
    

def hit(self, timestamp: int) -> None:
    """
    Record a hit.
    @param timestamp - The current timestamp (in seconds granularity).
    """
    if timestamp not in self.hits:
        self.hits[timestamp] = 0
    self.hits[timestamp] += 1
    

def getHits(self, timestamp: int) -> int:
    """
    Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity).
    """
    begin = timestamp - 300
    hits_for_ts = 0
    for i in range(begin+1, timestamp+1):
        if i in self.hits:
            hits_for_ts += self.hits[i]
    return hits_for_ts

getHits is still constant time, as it is always looping 300 times (this is negligible when you have millions of timestamp). The proposed solution does similar stuff but seems overly complex

Deque solution approach #2 is not really optimized for space. You can reduce space complexity to O(1), since at any given time you need to keep at max 300 pairs. Solution is to also do pop while registering the hit and therefore maintaining a constant space complexity. Remember always popping is capped to 300 in both hit() and getHits() API.

How come the official solution is not the most optimized one?

I posted a solution where hit function time complexity is O(1) and getHits func time complexity is O(log n) - https://leetcode.com/problems/design-hit-counter/discuss/1068290/C%2B%2B-w-full-explanation.-Beats-100-runtime.-hit-func-O(1)-and-getHits-func-O(logn)

This should be mark easy

Short c++ solution (20 lines).
Time complexity: hit O(1) ; getHits O(logN).
Space used O(n).
What do you think about it?

class HitCounter {
public:
    void hit(int timestamp) {
        hits.push_back(timestamp);

        // Prevent overloading.
        if (hits.front() < timestamp - 300)
            hits.pop_front();
    }

    int getHits(int timestamp) {
        auto it = upper_bound(hits.begin(), hits.end(), timestamp - 300);

        return hits.end() - it;
    }

private:
    deque<int> hits;
};

A scalable and fast circular buffer solution:

https://leetcode.com/problems/design-hit-counter/discuss/1111730/Scalable-Circular-Buffer-Solution

Simple solution using map in Go which also accounts for concurrent hits.

type HitCounter struct {
	mu   sync.Mutex
	hits map[int]int
}

/** Initialize your data structure here. */
func Constructor() HitCounter {
	return HitCounter{
		hits: make(map[int]int),
	}
}

/** Record a hit.
  @param timestamp - The current timestamp (in seconds granularity). */
func (this *HitCounter) Hit(timestamp int) {
	this.mu.Lock()
	this.hits[timestamp] = this.hits[timestamp] + 1
	this.mu.Unlock()
}

/** Return the number of hits in the past 5 minutes.
  @param timestamp - The current timestamp (in seconds granularity). */
func (this *HitCounter) GetHits(timestamp int) int {
	this.mu.Lock()
	defer this.mu.Unlock()
	var start = timestamp - 299
	if start < 0 {
		start = 1
	}
	var noOfHits int
	for i := start; i <= timestamp; i++ {
		noOfHits = noOfHits + this.hits[i]
	}
	return noOfHits
}

I believe there is an error in the C++ solution 2 -- It explains using a deque, but it does not, and in the hit() method it checks the .front() rather than the .back()

space complexity can be reduced to o(1)

Java solution using Map

import java.util.Optional;

class HitCounter {

    private Map<Integer, Integer> hitMap;
    /** Initialize your data structure here. */
    public HitCounter() {
        hitMap = new HashMap<>();
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        if(hitMap.containsKey(timestamp)) {
            hitMap.put(timestamp, hitMap.get(timestamp)+1);
        } else {
            hitMap.put(timestamp, 1);
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        Optional<Integer> hits;
        
        if(timestamp <= 300) {
            // Find all the entries in the map from the range 1 to 300
             hits = hitMap.entrySet().stream()
                    .filter(e -> e.getKey() <= 300)
                    .map(Map.Entry::getValue)
                    .reduce(Integer::sum);
        } else {
            // Find all the entries in the map from the range timestamp to timestamp-300
            // timestamp-300
            hits = hitMap.entrySet().stream()
                    .filter(e -> e.getKey() > timestamp - 300)
                    .map(Map.Entry::getValue)
                    .reduce(Integer::sum);
        }
        if(hits.isPresent())
            return hits.get();
        else 
            return 0;
    }
}